# -*- coding: utf-8 -*-
"""
Functional notation

These are functions so that you can write foo(x) instead of x.foo()
in certain common cases.

AUTHORS:

- William Stein: Initial version

- David Joyner (2005-12-20): More Examples
"""

#*****************************************************************************
#       Copyright (C) 2004 William Stein <wstein@gmail.com>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 2 of the License, or
# (at your option) any later version.
#                  http://www.gnu.org/licenses/
#*****************************************************************************

import sage.misc.latex
import sage.interfaces.expect
import sage.interfaces.mathematica


from sage.rings.complex_double import CDF
from sage.rings.real_double import RDF, RealDoubleElement

import sage.rings.real_mpfr
import sage.rings.complex_field
import sage.rings.integer

import __builtin__

LOG_TEN_TWO_PLUS_EPSILON = 3.321928094887363 # a small overestimate of log(10,2)

##############################################################################
# There are many functions on elements of a ring, which mathematicians
# usually write f(x), e.g., it is weird to write x.log() and natural
# to write log(x).  The functions below allow for the more familiar syntax.
##############################################################################
def additive_order(x):
    """
    Returns the additive order of `x`.

    EXAMPLES::

        sage: additive_order(5)
        +Infinity
        sage: additive_order(Mod(5,11))
        11
        sage: additive_order(Mod(4,12))
        3
    """
    return x.additive_order()

def base_ring(x):
    """
    Returns the base ring over which x is defined.

    EXAMPLES::

        sage: R = PolynomialRing(GF(7), 'x')
        sage: base_ring(R)
        Finite Field of size 7
    """
    return x.base_ring()

def base_field(x):
    """
    Returns the base field over which x is defined.

    EXAMPLES::

        sage: R = PolynomialRing(GF(7), 'x')
        sage: base_ring(R)
        Finite Field of size 7
        sage: base_field(R)
        Finite Field of size 7

    This catches base rings which are fields as well, but does
    not implement a ``base_field`` method for objects which do
    not have one::

        sage: R.base_field()
        Traceback (most recent call last):
        ...
        AttributeError: 'PolynomialRing_dense_mod_p_with_category' object has no attribute 'base_field'
    """
    try:
        return x.base_field()
    except AttributeError:
        y = x.base_ring()
        if is_field(y):
            return y
        else:
            raise AttributeError("The base ring of %s is not a field"%x)

def basis(x):
    """
    Returns the fixed basis of x.

    EXAMPLES::

        sage: V = VectorSpace(QQ,3)
        sage: S = V.subspace([[1,2,0],[2,2,-1]])
        sage: basis(S)
        [
        (1, 0, -1),
        (0, 1, 1/2)
        ]
    """
    return x.basis()

def category(x):
    """
    Returns the category of x.

    EXAMPLES::

        sage: V = VectorSpace(QQ,3)
        sage: category(V)
        Category of finite dimensional vector spaces with basis over
         (quotient fields and metric spaces)
    """
    try:
        return x.category()
    except AttributeError:
        import sage.categories.all
        return sage.categories.all.Objects()


def characteristic_polynomial(x, var='x'):
    """
    Returns the characteristic polynomial of x in the given variable.

    EXAMPLES::

        sage: M = MatrixSpace(QQ,3,3)
        sage: A = M([1,2,3,4,5,6,7,8,9])
        sage: charpoly(A)
        x^3 - 15*x^2 - 18*x
        sage: charpoly(A, 't')
        t^3 - 15*t^2 - 18*t

    ::

        sage: k.<alpha> = GF(7^10); k
        Finite Field in alpha of size 7^10
        sage: alpha.charpoly('T')
        T^10 + T^6 + T^5 + 4*T^4 + T^3 + 2*T^2 + 3*T + 3
        sage: characteristic_polynomial(alpha, 'T')
        T^10 + T^6 + T^5 + 4*T^4 + T^3 + 2*T^2 + 3*T + 3

    Ensure the variable name of the polynomial does not conflict with
    variables used within the matrix, and that non-integral powers of
    variables don't confuse the computation (:trac:`14403`)::

        sage: y = var('y')
        sage: a = matrix([[x,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]])
        sage: characteristic_polynomial(a).list()
        [x, -3*x - 1, 3*x + 3, -x - 3, 1]
        sage: b = matrix([[y^(1/2),0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]])
        sage: charpoly(b).list()
        [sqrt(y), -3*sqrt(y) - 1, 3*sqrt(y) + 3, -sqrt(y) - 3, 1]
    """
    try:
        return x.charpoly(var)
    except AttributeError:
        raise NotImplementedError("computation of charpoly of x (={}) not implemented".format(x))

charpoly = characteristic_polynomial


def coerce(P, x):
    """
    Attempts to coerce x to type P if possible.

    EXAMPLES::

        sage: type(5)
        <type 'sage.rings.integer.Integer'>
        sage: type(coerce(QQ,5))
        <type 'sage.rings.rational.Rational'>
    """
    try:
        return P._coerce_(x)
    except AttributeError:
        return P(x)

def cyclotomic_polynomial(n, var='x'):
    """
    Returns the `n^{th}` cyclotomic polynomial.

    EXAMPLES::

        sage: cyclotomic_polynomial(3)
        x^2 + x + 1
        sage: cyclotomic_polynomial(4)
        x^2 + 1
        sage: cyclotomic_polynomial(9)
        x^6 + x^3 + 1
        sage: cyclotomic_polynomial(10)
        x^4 - x^3 + x^2 - x + 1
        sage: cyclotomic_polynomial(11)
        x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
    """
    return sage.rings.all.ZZ[var].cyclotomic_polynomial(n)

def decomposition(x):
    """
    Returns the decomposition of x.

    EXAMPLES::

        sage: M = matrix([[2, 3], [3, 4]])
        sage: M.decomposition()
        [
        (Ambient free module of rank 2 over the principal ideal domain Integer Ring, True)
        ]

    ::

        sage: G.<a,b> = DirichletGroup(20)
        sage: c = a*b
        sage: d = c.decomposition(); d
        [Dirichlet character modulo 4 of conductor 4 mapping 3 |--> -1,
        Dirichlet character modulo 5 of conductor 5 mapping 2 |--> zeta4]
        sage: d[0].parent()
        Group of Dirichlet characters modulo 4 with values in Cyclotomic Field of order 4 and degree 2
    """
    return x.decomposition()

def denominator(x):
    """
    Returns the denominator of x.

    EXAMPLES::

        sage: denominator(17/11111)
        11111
        sage: R.<x> = PolynomialRing(QQ)
        sage: F = FractionField(R)
        sage: r = (x+1)/(x-1)
        sage: denominator(r)
        x - 1
    """
    if isinstance(x, (int, long)):
        return 1
    return x.denominator()

def det(x):
    """
    Returns the determinant of x.

    EXAMPLES::

        sage: M = MatrixSpace(QQ,3,3)
        sage: A = M([1,2,3,4,5,6,7,8,9])
        sage: det(A)
        0
    """
    return x.det()

def dimension(x):
    """
    Returns the dimension of x.

    EXAMPLES::

        sage: V = VectorSpace(QQ,3)
        sage: S = V.subspace([[1,2,0],[2,2,-1]])
        sage: dimension(S)
        2
    """
    return x.dimension()

dim = dimension

def discriminant(x):
    """
    Returns the discriminant of x.

    EXAMPLES::

        sage: R.<x> = PolynomialRing(QQ)
        sage: S = R.quotient(x^29 - 17*x - 1, 'alpha')
        sage: K = S.number_field()
        sage: discriminant(K)
        -15975100446626038280218213241591829458737190477345113376757479850566957249523
    """
    return x.discriminant()

disc = discriminant


def eta(x):
    r"""
    Returns the value of the eta function at `x`, which must be
    in the upper half plane.

    The `\eta` function is

    .. math::

                    \eta(z) = e^{\pi i z / 12} \prod_{n=1}^{\infty}(1-e^{2\pi inz})

    EXAMPLES::

        sage: eta(1+I)
        0.7420487758365647 + 0.1988313702299107*I
    """
    try: return x.eta()
    except AttributeError: return CDF(x).eta()


def fcp(x, var='x'):
    """
    Returns the factorization of the characteristic polynomial of x.

    EXAMPLES::

        sage: M = MatrixSpace(QQ,3,3)
        sage: A = M([1,2,3,4,5,6,7,8,9])
        sage: fcp(A, 'x')
        x * (x^2 - 15*x - 18)
    """
    try: return x.fcp(var)
    except AttributeError: return charpoly(x, var).factor()


def gen(x):
    """
    Returns the generator of x.

    EXAMPLES::

        sage: R.<x> = QQ[]; R
        Univariate Polynomial Ring in x over Rational Field
        sage: gen(R)
        x
        sage: gen(GF(7))
        1
        sage: A = AbelianGroup(1, [23])
        sage: gen(A)
        f
    """
    return x.gen()

def gens(x):
    """
    Returns the generators of x.

    EXAMPLES::

        sage: R.<x,y> = SR[]
        sage: R
        Multivariate Polynomial Ring in x, y over Symbolic Ring
        sage: gens(R)
        (x, y)
        sage: A = AbelianGroup(5, [5,5,7,8,9])
        sage: gens(A)
        (f0, f1, f2, f3, f4)
    """
    return x.gens()

def hecke_operator(x,n):
    """
    Returns the n-th Hecke operator T_n acting on x.

    EXAMPLES::

        sage: M = ModularSymbols(1,12)
        sage: hecke_operator(M,5)
        Hecke operator T_5 on Modular Symbols space of dimension 3 for Gamma_0(1) of weight 12 with sign 0 over Rational Field
    """
    return x.hecke_operator(n)


def image(x):
    """
    Returns the image of x.

    EXAMPLES::

        sage: M = MatrixSpace(QQ,3,3)
        sage: A = M([1,2,3,4,5,6,7,8,9])
        sage: image(A)
        Vector space of degree 3 and dimension 2 over Rational Field
        Basis matrix:
        [ 1  0 -1]
        [ 0  1  2]
    """
    return x.image()

def symbolic_sum(expression, *args, **kwds):
    r"""
    Returns the symbolic sum `\sum_{v = a}^b expression` with respect
    to the variable `v` with endpoints `a` and `b`.

    INPUT:

    - ``expression`` - a symbolic expression

    - ``v`` - a variable or variable name

    - ``a`` - lower endpoint of the sum

    - ``b`` - upper endpoint of the sum

    - ``algorithm`` - (default: ``'maxima'``)  one of

      - ``'maxima'`` - use Maxima (the default)

      - ``'maple'`` - (optional) use Maple

      - ``'mathematica'`` - (optional) use Mathematica

      - ``'giac'`` - (optional) use Giac

    EXAMPLES::

        sage: k, n = var('k,n')
        sage: sum(k, k, 1, n).factor()
        1/2*(n + 1)*n

    ::

        sage: sum(1/k^4, k, 1, oo)
        1/90*pi^4

    ::

        sage: sum(1/k^5, k, 1, oo)
        zeta(5)

    .. WARNING::

        This function only works with symbolic expressions. To sum any
        other objects like list elements or function return values,
        please use python summation, see
        http://docs.python.org/library/functions.html#sum

        In particular, this does not work::

            sage: n = var('n')
            sage: list=[1,2,3,4,5]
            sage: sum(list[n],n,0,3)
            Traceback (most recent call last):
            ...
            TypeError: unable to convert n to an integer
            
        Use python ``sum()`` instead::

            sage: sum(list[n] for n in range(4))
            10
            
        Also, only a limited number of functions are recognized in symbolic sums::

            sage: sum(valuation(n,2),n,1,5)
            Traceback (most recent call last):
            ...
            TypeError: unable to convert n to an integer
            
        Again, use python ``sum()``::
        
            sage: sum(valuation(n+1,2) for n in range(5))
            3
            
        (now back to the Sage ``sum`` examples)

    A well known binomial identity::

        sage: sum(binomial(n,k), k, 0, n)
        2^n

    The binomial theorem::

        sage: x, y = var('x, y')
        sage: sum(binomial(n,k) * x^k * y^(n-k), k, 0, n)
        (x + y)^n

    ::

        sage: sum(k * binomial(n, k), k, 1, n)
        2^(n - 1)*n

    ::

        sage: sum((-1)^k*binomial(n,k), k, 0, n)
        0

    ::

        sage: sum(2^(-k)/(k*(k+1)), k, 1, oo)
        -log(2) + 1

    Another binomial identity (:trac:`7952`)::

        sage: t,k,i = var('t,k,i')
        sage: sum(binomial(i+t,t),i,0,k)
        binomial(k + t + 1, t + 1)

    Summing a hypergeometric term::

        sage: sum(binomial(n, k) * factorial(k) / factorial(n+1+k), k, 0, n)
        1/2*sqrt(pi)/factorial(n + 1/2)

    We check a well known identity::

        sage: bool(sum(k^3, k, 1, n) == sum(k, k, 1, n)^2)
        True

    A geometric sum::

        sage: a, q = var('a, q')
        sage: sum(a*q^k, k, 0, n)
        (a*q^(n + 1) - a)/(q - 1)

    The geometric series::

        sage: assume(abs(q) < 1)
        sage: sum(a*q^k, k, 0, oo)
        -a/(q - 1)

    A divergent geometric series.  Don't forget
    to forget your assumptions::

        sage: forget()
        sage: assume(q > 1)
        sage: sum(a*q^k, k, 0, oo)
        Traceback (most recent call last):
        ...
        ValueError: Sum is divergent.

    This summation only Mathematica can perform::

        sage: sum(1/(1+k^2), k, -oo, oo, algorithm = 'mathematica')     # optional - mathematica
        pi*coth(pi)

    Use Maple as a backend for summation::

        sage: sum(binomial(n,k)*x^k, k, 0, n, algorithm = 'maple')      # optional - maple
        (x + 1)^n

    Python ints should work as limits of summation (:trac:`9393`)::

        sage: sum(x, x, 1r, 5r)
        15

    .. note::

       #. Sage can currently only understand a subset of the output of Maxima, Maple and
          Mathematica, so even if the chosen backend can perform the summation the
          result might not be convertable into a Sage expression.

    """
    if hasattr(expression, 'sum'):
        return expression.sum(*args, **kwds)
    elif len(args) <= 1:
        return sum(expression, *args)
    else:
        from sage.symbolic.ring import SR
        return SR(expression).sum(*args, **kwds)


def integral(x, *args, **kwds):
    """
    Returns an indefinite or definite integral of an object x.

    First call x.integral() and if that fails make an object and
    integrate it using Maxima, maple, etc, as specified by algorithm.

    For symbolic expression calls
    :func:`sage.calculus.calculus.integral` - see this function for
    available options.

    EXAMPLES::

        sage: f = cyclotomic_polynomial(10)
        sage: integral(f)
        1/5*x^5 - 1/4*x^4 + 1/3*x^3 - 1/2*x^2 + x

    ::

        sage: integral(sin(x),x)
        -cos(x)

    ::

        sage: y = var('y')
        sage: integral(sin(x),y)
        y*sin(x)

    ::

        sage: integral(sin(x), x, 0, pi/2)
        1
        sage: sin(x).integral(x, 0,pi/2)
        1
        sage: integral(exp(-x), (x, 1, oo))
        e^(-1)

    Numerical approximation::

        sage: h = integral(tan(x)/x, (x, 1, pi/3)); h
        integrate(tan(x)/x, x, 1, 1/3*pi)
        sage: h.n()
        0.07571599101...

    Specific algorithm can be used for integration::

        sage: integral(sin(x)^2, x, algorithm='maxima')
        1/2*x - 1/4*sin(2*x)
        sage: integral(sin(x)^2, x, algorithm='sympy')
        -1/2*cos(x)*sin(x) + 1/2*x

    TESTS:

    A symbolic integral from :trac:`11445` that was incorrect in
    earlier versions of Maxima::

        sage: f = abs(x - 1) + abs(x + 1) - 2*abs(x)
        sage: integrate(f, (x, -Infinity, Infinity))
        2

    Another symbolic integral, from :trac:`11238`, that used to return
    zero incorrectly; with Maxima 5.26.0 one gets
    ``1/2*sqrt(pi)*e^(1/4)``, whereas with 5.29.1, and even more so
    with 5.33.0, the expression is less pleasant, but still has the
    same value.  Unfortunately, the computation takes a very long time
    with the default settings, so we temporarily use the Maxima
    setting ``domain: real``::

        sage: sage.calculus.calculus.maxima('domain: real')
        real
        sage: f = exp(-x) * sinh(sqrt(x))
        sage: t = integrate(f, x, 0, Infinity); t            # long time
        1/4*sqrt(pi)*(erf(1) - 1)*e^(1/4) - 1/4*(sqrt(pi)*(erf(1) - 1) - sqrt(pi) + 2*e^(-1) - 2)*e^(1/4) + 1/4*sqrt(pi)*e^(1/4) - 1/2*e^(1/4) + 1/2*e^(-3/4)
        sage: t.canonicalize_radical()  # long time
        1/2*sqrt(pi)*e^(1/4)
        sage: sage.calculus.calculus.maxima('domain: complex')
        complex

    An integral which used to return -1 before maxima 5.28. See :trac:`12842`::

        sage: f = e^(-2*x)/sqrt(1-e^(-2*x))
        sage: integrate(f, x, 0, infinity)
        1

    This integral would cause a stack overflow in earlier versions of
    Maxima, crashing sage. See :trac:`12377`. We don't care about the
    result here, just that the computation completes successfully::

        sage: y = (x^2)*exp(x) / (1 + exp(x))^2
        sage: _ = integrate(y, x, -1000, 1000)

    """
    if hasattr(x, 'integral'):
        return x.integral(*args, **kwds)
    else:
        from sage.symbolic.ring import SR
        return SR(x).integral(*args, **kwds)

integrate = integral


def integral_closure(x):
    """
    Returns the integral closure of x.

    EXAMPLES::

        sage: integral_closure(QQ)
        Rational Field
        sage: K.<a> = QuadraticField(5)
        sage: O2 = K.order(2*a); O2
        Order in Number Field in a with defining polynomial x^2 - 5
        sage: integral_closure(O2)
        Maximal Order in Number Field in a with defining polynomial x^2 - 5
    """
    return x.integral_closure()

def interval(a, b):
    r"""
    Integers between a and b *inclusive* (a and b integers).

    EXAMPLES::

        sage: I = interval(1,3)
        sage: 2 in I
        True
        sage: 1 in I
        True
        sage: 4 in I
        False
    """
    return range(a,b+1)

def xinterval(a, b):
    r"""
    Iterator over the integers between a and b, *inclusive*.

    EXAMPLES::

        sage: I = xinterval(2,5); I
        xrange(2, 6)
        sage: 5 in I
        True
        sage: 6 in I
        False
    """
    return xrange(a, b+1)

def is_commutative(x):
    """
    Returns whether or not x is commutative.

    EXAMPLES::

        sage: R = PolynomialRing(QQ, 'x')
        sage: is_commutative(R)
        True
    """
    return x.is_commutative()

def is_even(x):
    """
    Returns whether or not an integer x is even, e.g., divisible by 2.

    EXAMPLES::

        sage: is_even(-1)
        False
        sage: is_even(4)
        True
        sage: is_even(-2)
        True
    """
    try: return x.is_even()
    except AttributeError: return x%2==0

def is_integrally_closed(x):
    """
    Returns whether x is integrally closed.

    EXAMPLES::

        sage: is_integrally_closed(QQ)
        True
        sage: K.<a> = NumberField(x^2 + 189*x + 394)
        sage: R = K.order(2*a)
        sage: is_integrally_closed(R)
        False
    """
    return x.is_integrally_closed()

def is_field(x):
    """
    Returns whether or not x is a field.

    EXAMPLES::

        sage: R = PolynomialRing(QQ, 'x')
        sage: F = FractionField(R)
        sage: is_field(F)
        True
    """
    return x.is_field()


def is_odd(x):
    """
    Returns whether or not x is odd. This is by definition the
    complement of is_even.

    EXAMPLES::

        sage: is_odd(-2)
        False
        sage: is_odd(-3)
        True
        sage: is_odd(0)
        False
        sage: is_odd(1)
        True
    """
    return not is_even(x)


def kernel(x):
    """
    Returns the left kernel of x.

    EXAMPLES::

        sage: M = MatrixSpace(QQ,3,2)
        sage: A = M([1,2,3,4,5,6])
        sage: kernel(A)
        Vector space of degree 3 and dimension 1 over Rational Field
        Basis matrix:
        [ 1 -2  1]
        sage: kernel(A.transpose())
        Vector space of degree 2 and dimension 0 over Rational Field
        Basis matrix:
        []

    Here are two corner cases:
        sage: M=MatrixSpace(QQ,0,3)
        sage: A=M([])
        sage: kernel(A)
        Vector space of degree 0 and dimension 0 over Rational Field
        Basis matrix:
        []
        sage: kernel(A.transpose()).basis()
        [
        (1, 0, 0),
        (0, 1, 0),
        (0, 0, 1)
        ]
    """
    return x.kernel()

def krull_dimension(x):
    """
    Returns the Krull dimension of x.

    EXAMPLES::

        sage: krull_dimension(QQ)
        0
        sage: krull_dimension(ZZ)
        1
        sage: krull_dimension(ZZ[sqrt(5)])
        1
        sage: U.<x,y,z> = PolynomialRing(ZZ,3); U
        Multivariate Polynomial Ring in x, y, z over Integer Ring
        sage: U.krull_dimension()
        4
    """
    return x.krull_dimension()

def lift(x):
    """
    Lift an object of a quotient ring `R/I` to `R`.

    EXAMPLES: We lift an integer modulo `3`.

    ::

        sage: Mod(2,3).lift()
        2

    We lift an element of a quotient polynomial ring.

    ::

        sage: R.<x> = QQ['x']
        sage: S.<xmod> = R.quo(x^2 + 1)
        sage: lift(xmod-7)
        x - 7
    """
    try:
        return x.lift()
    except AttributeError:
        raise ArithmeticError("no lift defined.")

def log(x,b=None):
    r"""
    Returns the log of x to the base b. The default base is e.

    INPUT:


    -  ``x`` - number

    -  ``b`` - base (default: None, which means natural
       log)


    OUTPUT: number

    .. note::

       In Magma, the order of arguments is reversed from in Sage,
       i.e., the base is given first. We use the opposite ordering, so
       the base can be viewed as an optional second argument.

    EXAMPLES::

        sage: log(e^2)
        2
        sage: log(16,2)
        4
        sage: log(3.)
        1.09861228866811
    """
    if b is None:
        if hasattr(x, 'log'):
            return x.log()
        return RDF(x)._log_base(1)
    else:
        if hasattr(x, 'log'):
            return x.log(b)
        return RDF(x).log(b)

def minimal_polynomial(x, var='x'):
    """
    Returns the minimal polynomial of x.

    EXAMPLES::

        sage: a = matrix(ZZ, 2, [1..4])
        sage: minpoly(a)
        x^2 - 5*x - 2
        sage: minpoly(a,'t')
        t^2 - 5*t - 2
        sage: minimal_polynomial(a)
        x^2 - 5*x - 2
        sage: minimal_polynomial(a,'theta')
        theta^2 - 5*theta - 2
    """
    try:
        return x.minpoly(var=var)
    except AttributeError:
        return x.minimal_polynomial(var=var)

minpoly = minimal_polynomial


def multiplicative_order(x):
    r"""
    Returns the multiplicative order of self, if self is a unit, or
    raise ``ArithmeticError`` otherwise.

    EXAMPLES::

        sage: a = mod(5,11)
        sage: multiplicative_order(a)
        5
        sage: multiplicative_order(mod(2,11))
        10
        sage: multiplicative_order(mod(2,12))
        Traceback (most recent call last):
        ...
        ArithmeticError: multiplicative order of 2 not defined since it is not a unit modulo 12
    """
    return x.multiplicative_order()


def ngens(x):
    """
    Returns the number of generators of x.

    EXAMPLES::

        sage: R.<x,y> = SR[]; R
        Multivariate Polynomial Ring in x, y over Symbolic Ring
        sage: ngens(R)
        2
        sage: A = AbelianGroup(5, [5,5,7,8,9])
        sage: ngens(A)
        5
        sage: ngens(ZZ)
        1
    """
    return x.ngens()

def norm(x):
    r"""
    Returns the norm of ``x``.

    For matrices and vectors, this returns the L2-norm. The L2-norm of a
    vector `\textbf{v} = (v_1, v_2, \dots, v_n)`, also called the Euclidean
    norm, is defined as

    .. MATH::

        |\textbf{v}|
        =
        \sqrt{\sum_{i=1}^n |v_i|^2}

    where `|v_i|` is the complex modulus of `v_i`. The Euclidean norm is often
    used for determining the distance between two points in two- or
    three-dimensional space.

    For complex numbers, the function returns the field norm. If
    `c = a + bi` is a complex number, then the norm of `c` is defined as the
    product of `c` and its complex conjugate

    .. MATH::

        \text{norm}(c)
        =
        \text{norm}(a + bi)
        =
        c \cdot \overline{c}
        =
        a^2 + b^2.

    The norm of a complex number is different from its absolute value.
    The absolute value of a complex number is defined to be the square
    root of its norm. A typical use of the complex norm is in the
    integral domain `\ZZ[i]` of Gaussian integers, where the norm of
    each Gaussian integer `c = a + bi` is defined as its complex norm.

    .. SEEALSO::

        - :meth:`sage.matrix.matrix2.Matrix.norm`

        - :meth:`sage.modules.free_module_element.FreeModuleElement.norm`

        - :meth:`sage.rings.complex_double.ComplexDoubleElement.norm`

        - :meth:`sage.rings.complex_number.ComplexNumber.norm`

        - :meth:`sage.symbolic.expression.Expression.norm`

    EXAMPLES:

    The norm of vectors::

        sage: z = 1 + 2*I
        sage: norm(vector([z]))
        sqrt(5)
        sage: v = vector([-1,2,3])
        sage: norm(v)
        sqrt(14)
        sage: _ = var("a b c d", domain='real')
        sage: v = vector([a, b, c, d])
        sage: norm(v)
        sqrt(a^2 + b^2 + c^2 + d^2)

    The norm of matrices::

        sage: z = 1 + 2*I
        sage: norm(matrix([[z]]))
        2.23606797749979
        sage: M = matrix(ZZ, [[1,2,4,3], [-1,0,3,-10]])
        sage: norm(M)  # abs tol 1e-14
        10.690331129154467
        sage: norm(CDF(z))
        5.0
        sage: norm(CC(z))
        5.00000000000000

    The norm of complex numbers::

        sage: z = 2 - 3*I
        sage: norm(z)
        13
        sage: a = randint(-10^10, 100^10)
        sage: b = randint(-10^10, 100^10)
        sage: z = a + b*I
        sage: bool(norm(z) == a^2 + b^2)
        True

    The complex norm of symbolic expressions::

        sage: a, b, c = var("a, b, c")
        sage: assume((a, 'real'), (b, 'real'), (c, 'real'))
        sage: z = a + b*I
        sage: bool(norm(z).simplify() == a^2 + b^2)
        True
        sage: norm(a + b).simplify()
        a^2 + 2*a*b + b^2
        sage: v = vector([a, b, c])
        sage: bool(norm(v).simplify() == sqrt(a^2 + b^2 + c^2))
        True
        sage: forget()
    """
    return x.norm()

def numerator(x):
    """
    Returns the numerator of x.

    EXAMPLES::

        sage: R.<x> = PolynomialRing(QQ)
        sage: F = FractionField(R)
        sage: r = (x+1)/(x-1)
        sage: numerator(r)
        x + 1
        sage: numerator(17/11111)
        17
    """
    if isinstance(x, (int, long)):
        return x
    return x.numerator()

# Following is the top-level numerical_approx function.
# Implement a ._numerical_approx(prec, digits, algorithm) method for your
# objects to enable the three top-level functions and three methods

def numerical_approx(x, prec=None, digits=None, algorithm=None):
    r"""
    Returns a numerical approximation of an object ``x`` with at
    least ``prec`` bits (or decimal ``digits``) of precision.

    .. note::

       Both upper case ``N`` and lower case ``n`` are aliases for
       :func:`numerical_approx`, and all three may be used as
       methods.

    INPUT:

    -  ``x`` - an object that has a numerical_approx
       method, or can be coerced into a real or complex field
    -  ``prec`` (optional) - an integer (bits of
       precision)
    -  ``digits`` (optional) - an integer (digits of
       precision)
    -  ``algorithm`` (optional) - a string specifying
       the algorithm to use for functions that implement
       more than one

    If neither the ``prec`` or ``digits`` are specified,
    the default is 53 bits of precision.  If both are
    specified, then ``prec`` is used.

    EXAMPLES::

        sage: numerical_approx(pi, 10)
        3.1
        sage: numerical_approx(pi, digits=10)
        3.141592654
        sage: numerical_approx(pi^2 + e, digits=20)
        12.587886229548403854
        sage: n(pi^2 + e)
        12.5878862295484
        sage: N(pi^2 + e)
        12.5878862295484
        sage: n(pi^2 + e, digits=50)
        12.587886229548403854194778471228813633070946500941
        sage: a = CC(-5).n(prec=40)
        sage: b = ComplexField(40)(-5)
        sage: a == b
        True
        sage: parent(a) is parent(b)
        True
        sage: numerical_approx(9)
        9.00000000000000

    You can also usually use method notation.  ::

        sage: (pi^2 + e).n()
        12.5878862295484
        sage: (pi^2 + e).N()
        12.5878862295484
        sage: (pi^2 + e).numerical_approx()
        12.5878862295484

    Vectors and matrices may also have their entries approximated.  ::

        sage: v = vector(RDF, [1,2,3])
        sage: v.n()
        (1.00000000000000, 2.00000000000000, 3.00000000000000)

        sage: v = vector(CDF, [1,2,3])
        sage: v.n()
        (1.00000000000000, 2.00000000000000, 3.00000000000000)
        sage: _.parent()
        Vector space of dimension 3 over Complex Field with 53 bits of precision
        sage: v.n(prec=20)
        (1.0000, 2.0000, 3.0000)

        sage: u = vector(QQ, [1/2, 1/3, 1/4])
        sage: n(u, prec=15)
        (0.5000, 0.3333, 0.2500)
        sage: n(u, digits=5)
        (0.50000, 0.33333, 0.25000)

        sage: v = vector(QQ, [1/2, 0, 0, 1/3, 0, 0, 0, 1/4], sparse=True)
        sage: u = v.numerical_approx(digits=4)
        sage: u.is_sparse()
        True
        sage: u
        (0.5000, 0.0000, 0.0000, 0.3333, 0.0000, 0.0000, 0.0000, 0.2500)

        sage: A = matrix(QQ, 2, 3, range(6))
        sage: A.n()
        [0.000000000000000  1.00000000000000  2.00000000000000]
        [ 3.00000000000000  4.00000000000000  5.00000000000000]

        sage: B = matrix(Integers(12), 3, 8, srange(24))
        sage: N(B, digits=2)
        [0.00  1.0  2.0  3.0  4.0  5.0  6.0  7.0]
        [ 8.0  9.0  10.  11. 0.00  1.0  2.0  3.0]
        [ 4.0  5.0  6.0  7.0  8.0  9.0  10.  11.]

    Internally, numerical approximations of real numbers are stored in base-2.
    Therefore, numbers which look the same in their decimal expansion might be
    different::

        sage: x=N(pi, digits=3); x
        3.14
        sage: y=N(3.14, digits=3); y
        3.14
        sage: x==y
        False
        sage: x.str(base=2)
        '11.001001000100'
        sage: y.str(base=2)
        '11.001000111101'

    Increasing the precision of a floating point number is not allowed::

        sage: CC(-5).n(prec=100)
        Traceback (most recent call last):
        ...
        TypeError: cannot approximate to a precision of 100 bits, use at most 53 bits
        sage: n(1.3r, digits=20)
        Traceback (most recent call last):
        ...
        TypeError: cannot approximate to a precision of 70 bits, use at most 53 bits
        sage: RealField(24).pi().n()
        Traceback (most recent call last):
        ...
        TypeError: cannot approximate to a precision of 53 bits, use at most 24 bits

    As an exceptional case, ``digits=1`` usually leads to 2 digits (one
    significant) in the decimal output (see :trac:`11647`)::

        sage: N(pi, digits=1)
        3.2
        sage: N(pi, digits=2)
        3.1
        sage: N(100*pi, digits=1)
        320.
        sage: N(100*pi, digits=2)
        310.

    In the following example, ``pi`` and ``3`` are both approximated to two
    bits of precision and then subtracted, which kills two bits of precision::

        sage: N(pi, prec=2)
        3.0
        sage: N(3, prec=2)
        3.0
        sage: N(pi - 3, prec=2)
        0.00

    TESTS::

        sage: numerical_approx(I)
        1.00000000000000*I
        sage: x = QQ['x'].gen()
        sage: F.<k> = NumberField(x^2+2, embedding=sqrt(CC(2))*CC.0)
        sage: numerical_approx(k)
        1.41421356237309*I

        sage: type(numerical_approx(CC(1/2)))
        <type 'sage.rings.complex_number.ComplexNumber'>

    The following tests :trac:`10761`, in which ``n()`` would break when
    called on complex-valued algebraic numbers.  ::

        sage: E = matrix(3, [3,1,6,5,2,9,7,3,13]).eigenvalues(); E
        [18.16815365088822?, -0.08407682544410650? - 0.2190261484802906?*I, -0.08407682544410650? + 0.2190261484802906?*I]
        sage: E[1].parent()
        Algebraic Field
        sage: [a.n() for a in E]
        [18.1681536508882, -0.0840768254441065 - 0.219026148480291*I, -0.0840768254441065 + 0.219026148480291*I]

    Make sure we've rounded up log(10,2) enough to guarantee
    sufficient precision (:trac:`10164`)::

        sage: ks = 4*10**5, 10**6
        sage: check_str_length = lambda k: len(str(numerical_approx(1+10**-k,digits=k+1)))-1 >= k+1
        sage: check_precision = lambda k: numerical_approx(1+10**-k,digits=k+1)-1 > 0
        sage: all(check_str_length(k) and check_precision(k) for k in ks)
        True

    Testing we have sufficient precision for the golden ratio (:trac:`12163`), note
    that the decimal point adds 1 to the string length::

        sage: len(str(n(golden_ratio, digits=5000)))
        5001
        sage: len(str(n(golden_ratio, digits=5000000)))  # long time (4s on sage.math, 2012)
        5000001

    Check that :trac:`14778` is fixed::

        sage: n(0, algorithm='foo')
        0.000000000000000
    """
    if prec is None:
        if digits is None:
            prec = 53
        else:
            prec = int((digits+1) * LOG_TEN_TWO_PLUS_EPSILON) + 1
    try:
        return x._numerical_approx(prec, algorithm=algorithm)
    except AttributeError:
        pass

    from sage.structure.element import parent
    B = parent(x)

    RR = sage.rings.real_mpfr.RealField(prec)
    map = RR.coerce_map_from(B)
    if map is not None:
        return map(x)
    CC = sage.rings.complex_field.ComplexField(prec)
    map = CC.coerce_map_from(B)
    if map is not None:
        return map(x)

    # Coercion didn't work: there are 3 possibilities:
    # (1) There is a coercion possible to a lower precision
    # (2) There is a conversion but no coercion
    # (3) The type doesn't convert at all

    # Figure out input precision to check for case (1)
    try:
        inprec = x.prec()
    except AttributeError:
        if prec > 53 and CDF.has_coerce_map_from(B):
            # If we can coerce to CDF, assume input precision was 53 bits
            inprec = 53
        else:
            # Otherwise, assume precision wasn't the issue
            inprec = prec

    if prec > inprec:
        raise TypeError("cannot approximate to a precision of %s bits, use at most %s bits" % (prec, inprec))

    # The issue is not precision, try conversion instead
    try:
        return RR(x)
    except (TypeError, ValueError):
        pass
    return CC(x)


n = numerical_approx
N = numerical_approx

def objgens(x):
    """
    EXAMPLES::

        sage: R, x = objgens(PolynomialRing(QQ,3, 'x'))
        sage: R
        Multivariate Polynomial Ring in x0, x1, x2 over Rational Field
        sage: x
        (x0, x1, x2)
    """
    return x.objgens()

def objgen(x):
    """
    EXAMPLES::

        sage: R, x = objgen(FractionField(QQ['x']))
        sage: R
        Fraction Field of Univariate Polynomial Ring in x over Rational Field
        sage: x
        x
    """
    return x.objgen()

def one(R):
    """
    Returns the one element of the ring R.

    EXAMPLES::

        sage: one(RR)
        doctest:...: DeprecationWarning: one(R) is deprecated, use R.one() or R(1) instead
        See http://trac.sagemath.org/17158 for details.
        1.00000000000000
        sage: R.<x> = PolynomialRing(QQ)
        sage: one(R)*x == x
        True
        sage: one(R) in R
        True
    """
    from sage.misc.superseded import deprecation
    deprecation(17158, 'one(R) is deprecated, use R.one() or R(1) instead')
    return R(1)

def order(x):
    """
    Returns the order of x. If x is a ring or module element, this is
    the additive order of x.

    EXAMPLES::

        sage: C = CyclicPermutationGroup(10)
        sage: order(C)
        10
        sage: F = GF(7)
        sage: order(F)
        7
    """
    return x.order()

def rank(x):
    """
    Returns the rank of x.

    EXAMPLES: We compute the rank of a matrix::

        sage: M = MatrixSpace(QQ,3,3)
        sage: A = M([1,2,3,4,5,6,7,8,9])
        sage: rank(A)
        2

    We compute the rank of an elliptic curve::

        sage: E = EllipticCurve([0,0,1,-1,0])
        sage: rank(E)
        1
    """
    return x.rank()

def regulator(x):
    """
    Returns the regulator of x.

    EXAMPLES::

        sage: regulator(NumberField(x^2-2, 'a'))
        0.881373587019543
        sage: regulator(EllipticCurve('11a'))
        1.00000000000000
    """
    return x.regulator()

def round(x, ndigits=0):
    """
    round(number[, ndigits]) - double-precision real number

    Round a number to a given precision in decimal digits (default 0
    digits). If no precision is specified this just calls the element's
    .round() method.

    EXAMPLES::

        sage: round(sqrt(2),2)
        1.41
        sage: q = round(sqrt(2),5); q
        1.41421
        sage: type(q)
        <type 'sage.rings.real_double.RealDoubleElement'>
        sage: q = round(sqrt(2)); q
        1
        sage: type(q)
        <type 'sage.rings.integer.Integer'>
        sage: round(pi)
        3
        sage: b = 5.4999999999999999
        sage: round(b)
        5


    Since we use floating-point with a limited range, some roundings can't
    be performed::

        sage: round(sqrt(Integer('1'*1000)),2)
        +infinity

    IMPLEMENTATION: If ndigits is specified, it calls Python's builtin
    round function, and converts the result to a real double field
    element. Otherwise, it tries the argument's .round() method; if
    that fails, it reverts to the builtin round function, converted to
    a real double field element.

    .. note::

       This is currently slower than the builtin round function, since
       it does more work - i.e., allocating an RDF element and
       initializing it. To access the builtin version do
       ``import __builtin__; __builtin__.round``.
    """
    try:
        if ndigits:
            return RealDoubleElement(__builtin__.round(x, ndigits))
        else:
            try:
                return x.round()
            except AttributeError:
                return RealDoubleElement(__builtin__.round(x, 0))
    except ArithmeticError:
        if not isinstance(x, RealDoubleElement):
            return round(RDF(x), ndigits)
        else:
            raise

def quotient(x, y, *args, **kwds):
    """
    Returns the quotient object x/y, e.g., a quotient of numbers or of a
    polynomial ring x by the ideal generated by y, etc.

    EXAMPLES::

        sage: quotient(5,6)
        5/6
        sage: quotient(5.,6.)
        0.833333333333333
        sage: R.<x> = ZZ[]; R
        Univariate Polynomial Ring in x over Integer Ring
        sage: I = Ideal(R, x^2+1)
        sage: quotient(R, I)
        Univariate Quotient Polynomial Ring in xbar over Integer Ring with modulus x^2 + 1
    """
    try:
        return x.quotient(y, *args, **kwds)
    except AttributeError:
        return x/y

quo = quotient


def isqrt(x):
    """
    Returns an integer square root, i.e., the floor of a square root.

    EXAMPLES::

        sage: isqrt(10)
        3
        sage: isqrt(10r)
        3
    """
    try:
        return x.isqrt()
    except AttributeError:
        from sage.functions.all import floor
        n = sage.rings.integer.Integer(floor(x))
        return n.isqrt()

def squarefree_part(x):
    """
    Returns the square free part of `x`, i.e., a divisor
    `z` such that `x = z y^2`, for a perfect square
    `y^2`.

    EXAMPLES::

        sage: squarefree_part(100)
        1
        sage: squarefree_part(12)
        3
        sage: squarefree_part(10)
        10
        sage: squarefree_part(216r) # see #8976
        6

    ::

        sage: x = QQ['x'].0
        sage: S = squarefree_part(-9*x*(x-6)^7*(x-3)^2); S
        -9*x^2 + 54*x
        sage: S.factor()
        (-9) * (x - 6) * x

    ::

        sage: f = (x^3 + x + 1)^3*(x-1); f
        x^10 - x^9 + 3*x^8 + 3*x^5 - 2*x^4 - x^3 - 2*x - 1
        sage: g = squarefree_part(f); g
        x^4 - x^3 + x^2 - 1
        sage: g.factor()
        (x - 1) * (x^3 + x + 1)
    """
    try:
        return x.squarefree_part()
    except AttributeError:
        pass
    from sage.arith.all import factor
    from sage.structure.all import parent
    F = factor(x)
    n = parent(x)(1)
    for p, e in F:
        if e%2 != 0:
            n *= p
    return n * F.unit()


def transpose(x):
    """
    Returns the transpose of x.

    EXAMPLES::

        sage: M = MatrixSpace(QQ,3,3)
        sage: A = M([1,2,3,4,5,6,7,8,9])
        sage: transpose(A)
        [1 4 7]
        [2 5 8]
        [3 6 9]
    """
    return x.transpose()


def zero(R):
    """
    Returns the zero element of the ring R.

    EXAMPLES::

        sage: zero(RR)
        doctest:...: DeprecationWarning: zero(R) is deprecated, use R.zero() or R(0) instead
        See http://trac.sagemath.org/17158 for details.
        0.000000000000000
        sage: R.<x> = PolynomialRing(QQ)
        sage: zero(R) in R
        True
        sage: zero(R)*x == zero(R)
        True
    """
    from sage.misc.superseded import deprecation
    deprecation(17158, 'zero(R) is deprecated, use R.zero() or R(0) instead')
    return R(0)
